/*************************************************************************
Program Name: bst.cpp
Des: This program initializes all the required functions to solve the
criminal cases which are used for finding out who is a criminal and who
is not one.
Author: Alberto De Pena
Due Date: 12/12/09 @ 11:55pm
*************************************************************************/
#include "bst.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

/*************************************************************************
Function Name: Root
Des: This function creates tree.
*************************************************************************/
Bst::Bst():Root(NULL)
{}

/*************************************************************************
Function Name: ~Bst
Des: Destroys the tree
*************************************************************************/
Bst::~Bst()
{
	//delete all the nodes in the tree using a postorder traversal
	PostOrderDestroy(Root);
	Root = NULL;
}

/*************************************************************************
Function Name: Bst Copy
Des: makes a copy of the actual tree and uses the copy for prunning.
*************************************************************************/

Bst::Bst(Bst & Source)
{
	Root = NULL;
	CopyTree(Source.Root);
}

/*************************************************************************
Function Name: CopyTree
Des: makes the copy of the tree.
*************************************************************************/
void Bst::CopyTree(TreePointer P)
{
	if (P != NULL)
	{
		Insert(P->info); //function which should already be in place
		CopyTree(P->left);
		CopyTree(P->right);
	}
}

/*************************************************************************
Function Name: Empty
Des: returns the root which is null, meaning that the tree is empty.
*************************************************************************/
bool Bst::Empty()
{
	return Root == NULL;
}

/*************************************************************************
Function Name: Insert
Des: This function uses a trailer pointer to insert a node in the correct
side and order of a tree.
*************************************************************************/
bool Bst::Insert(TreeType data)
{
	//create memory, if memory cannot be allocated, return with false
	TreePointer P = new Node;
	if (P == NULL)
		return false;

	//initialize the node, it will be a leaf so set the left and right
	//pointers to NULL
	P->info = data;
	P->right = P->left = NULL;

	//is this the first node to be inserted?  If it is then set the root
	//and return.
	if (Root == NULL)
	{
		Root = P;
		return true;
	}

	//Trailer pointer (parent) logic to find insertion point
	TreePointer Cur = Root, Parent = NULL;
	while (Cur != NULL)
	{
		Parent = Cur;
		if (data.Name <= Cur->info.Name)
			Cur = Cur->left;
		else
			Cur = Cur->right;
	}

	//Graft the node onto the correct side of the parent
	if (data.Name <= Parent->info.Name)
		Parent->left = P;
	else
		Parent->right = P;

	return true;
}

/*************************************************************************
Function Name: PostOrderDestroy
Des: This function uses a Post-Order Traversal to destroy a tree.
*************************************************************************/
void Bst::PostOrderDestroy(TreePointer P)
{
	if (P != NULL)
	{
		PostOrderDestroy(P->left);
		PostOrderDestroy(P->right);
		delete P;
	}
}

/*************************************************************************
Function Name: Print
Des: This function calls InOrderPrint to print a tree.
*************************************************************************/
void Bst::Print(ostream & crimfout)
{
	InOrderPrint(Root, crimfout);
}

/*************************************************************************
Function Name: InOrderPrint
Des: This function uses a In-Order Traversal to print the criminals in 
alphabetical order.
*************************************************************************/
void Bst::InOrderPrint(TreePointer P, ostream & crimfout)
{
	if (P != NULL)
	{
		InOrderPrint(P->left,crimfout);
		crimfout << P->info.Name << endl;
		InOrderPrint(P->right,crimfout);
	}
}

/*************************************************************************
Function Name: DeleteLeaf
Des: This function deletes a node that both pointer are NULL.
*************************************************************************/
void Bst::DeleteLeaf(TreePointer P, TreePointer Parent)
{
	//check for root
	if (Parent == NULL)
		Root = NULL;
	else
		if (Parent->left == P)
			Parent->left = NULL;
		else
			Parent->right = NULL;
	delete P;
}

/*************************************************************************
Function Name: DeleteOneChild
Des: This function deletes a node that either has right pointer NULL and
left pointer not NULL or right pointer not NULL and left pointer NULL.
*************************************************************************/
void Bst::DeleteOneChild(TreePointer P, TreePointer Parent)
{
	TreePointer Alive;

	if(P->left != NULL)
		Alive = P->left;
	else
		Alive = P->right;

	if(P == Root)
		Root = Alive;
	else
		if(Parent->left == P)
			Parent->left = Alive;
		else
			Parent->right = Alive;
	delete P;
}

/*************************************************************************
Function Name: DeleteTwoChild
Des: This function deletes a node that has left and right pointer not 
equal to NULL.
*************************************************************************/
void Bst::DeleteTwoChild(TreePointer P)
{
	TreePointer Predecessor, Parent;

	Predecessor = P->left;
	Parent = P;

	while(Predecessor->right != NULL)
	{
		Parent = Predecessor;
		Predecessor = Predecessor->right;
	}
	P->info = Predecessor->info;

	if(Predecessor->right == NULL && Predecessor->left == NULL)
		DeleteLeaf(Predecessor, Parent);
	else
		DeleteOneChild(Predecessor, Parent);
}

/*************************************************************************
Function Name: Prune
Des: This function calls PostOrderPrune.
*************************************************************************/
void Bst::Prune(string Tip)
{
	if(Root != NULL)
		PostOrderPrune(Tip, Root, NULL);
}

/*************************************************************************
Function Name: PostOrderPrune
Des: This function is responsible for calling the correct prunning funtion
to make sure the correct criminal is being deleted from the database.
*************************************************************************/
void Bst::PostOrderPrune(string Tip, TreePointer Current, TreePointer Parent)
{
	//(Left, Right) finds the appropriate node to prune
	if(Current->left != NULL)
		PostOrderPrune(Tip, Current->left, Current);
	
	if(Current->right != NULL)
		PostOrderPrune(Tip, Current->right, Current);
	
	//(visit) checks to see if the tip is present or not
	if(AttributeNotFound(Current, Tip))
	{
		if (Current->right == NULL && Current->left == NULL)
			DeleteLeaf(Current, Parent);
		else if (Current->right != NULL && Current->left != NULL)
			DeleteTwoChild(Current);
		else
			DeleteOneChild(Current, Parent);
	}
}

/*************************************************************************
Function Name: AttributeNotFound
Des: This function goes through the attributes found in the array of 
attributes of each criminal and compares it to the one given by the
casefile.  If the attribute is not found the it returns true.
*************************************************************************/
bool Bst::AttributeNotFound(TreePointer Current, string Tip)
{
	for(int a = 0; a < Current->info.AttributeCount; a++)
	{
		if(Current->info.Attribute[a] == Tip)
			return false;
	}
	return true;
}

